package lib


func init() {
	Probs = append(Probs, Problem{
		Num:         442,
		Discription: "n个数，数的范围为1...n，每个数均出现一次或者两次，找出出现了两次的数",
		Level:       2,
		Labels: map[string]int{
			"哈希表": 1,
			"空间复用": 1,
		},
	})
}

//思路：尝试把每个val放到索引为val-1的位置，放不下的就是多出来的
func FindDuplicates(nums []int) []int {
	for index, val := range nums {
		for val != index+1 && nums[val-1] != val {
			nums[index], nums[val-1] = nums[val-1], nums[index]
			val = nums[index]
		}
	}

	res := make([]int, 0)
	for i := range nums {
		if nums[i] != i+1 {
			res = append(res, nums[i])
		}
	}

	return res
}